package DFS;

/**
 * @Classname JZ13机器人的运动范围
 * @Description TODO
 * @Date 2023/3/2 21:23
 * @Created by xjl
 */
public class JZ13机器人的运动范围 {

    //记录遍历的四个方向
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    //记录答案
    int res = 0;

    //计算一个数字的每个数之和
    int cal(int n) {
        int sum = 0;
        //连除法算出每一位
        while (n != 0) {
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }

    //深度优先搜索dfs
    void dfs(int i, int j, int rows, int cols, int threshold, boolean[][] vis) {
        //越界或者已经访问过
        if (i < 0 || i >= rows || j < 0 || j >= cols || vis[i][j] == true) {
            return;
        }
        //行列和数字相加大于threshold，不可取
        if (cal(i) + cal(j) > threshold) {
            return;
        }
        res += 1;
        //标记经过的位置
        vis[i][j] = true;
        //上下左右四个方向搜索
        for (int k = 0; k < 4; k++) {
            dfs(i + dir[k][0], j + dir[k][1], rows, cols, threshold, vis);
        }
    }

    public int movingCount(int threshold, int rows, int cols) {
        //判断特殊情况
        if (threshold <= 0) {
            return 1;
        }
        //标记某个格子没有被访问过
        boolean[][] vis = new boolean[rows][cols];
        dfs(0, 0, rows, cols, threshold, vis);
        return res;
    }
}
